package e_BST;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

/**
 * @author lenovo
 *
 * 满二叉树的常用特性结论：高度为1，则每一层的节点数为2^(h-1) 比如第0层是一个； 总节点数目为：(2^h)-1
 *           对比之后可以发现一个很重要的结论： 1、满二叉树最后一层的节点数 比 前面所有层次的节点数之和 多1；即2^(h-1)+2^(h-1)-1 = 2^h-1(总节点数)
 *									2、假设一个二叉树的总结点数为2^k 则其h为k+1；怎么判断呢？高度为h的二叉树最多有(2^h)-1个节点，所以(2^h)-1>=2^k;(2^k>=1)
 *
 */

public class BST<E extends Comparable<E>> {

	private class Node {
		private E e;
		private Node left;
		private Node right;

		public Node(Node left, E e, Node right) {
			this.e = e;
			this.left = left;
			this.right = right;
		}

		public Node(Node left, E e) {
			this(left, e, null);
		}

		public Node(E e, Node right) {
			this(null, e, right);
		}

		public Node(E e) {
			this(null, e, null);
		}

		public boolean isLeaf() {
			return this.left == null && this.right == null;
		}

		@Override
		public String toString() {
			return this.e.toString();
		}

	}

	
	private Node root;
	private int size;

	public BST() {
		root = null;
		size = 0;
	}

	public int size() {
		return size;
	}

	public boolean isEmpty() {
		return size == 0;
	}

	// 向二分搜索树中添加新的元素e
	public void add(E e) {
		root = add(root, e);
	}

	// 向以node为根的二分搜索树中插入元素e，递归算法
	// 返回插入新节点后二分搜索树的根
	private Node add(Node node, E e) {

		if (node == null) {
			size++;
			return new Node(e);
		}

		if (e.compareTo(node.e) < 0)
			node.left = add(node.left, e);// 最后找到位置创建新节点的时候需要和其父节点挂接
		else if (e.compareTo(node.e) > 0)
			node.right = add(node.right, e);

		return node;
	}

	// 看二分搜索树中是否包含元素e
	public boolean contains(E e) {
		return contains(root, e);
	}

	// 看以node为根的二分搜索树中是否包含元素e, 递归算法
	private boolean contains(Node node, E e) {

		if (node == null)
			return false;

		if (e.compareTo(node.e) == 0)
			return true;
		else if (e.compareTo(node.e) < 0)
			return contains(node.left, e);
		else // e.compareTo(node.e) > 0
			return contains(node.right, e);
	}

	// 二分搜索树的前序遍历
	public void preOrder() {
		preOrder(root);
	}

	// 前序遍历以node为根的二分搜索树, 递归算法
	private void preOrder(Node node) {

		if (node == null)
			return;

		System.out.println(node.e);
		preOrder(node.left);
		preOrder(node.right);
	}

	// 二分搜索树的非递归前序遍历
	public void preOrderNR1() {

		Stack<Node> stack = new Stack<>();
		stack.push(root);
		while (!stack.isEmpty()) {
			Node cur = stack.pop();
			System.out.println(cur.e);

			if (cur.right != null)
				stack.push(cur.right);
			if (cur.left != null)
				stack.push(cur.left);
		}
	}

	public void preOrderNRtry() {
		// 模仿系统栈进行尝试改写，成功了
		Stack<Node> stack = new Stack<>();
		Node cur = root;
		while (cur != null || !stack.isEmpty()) {
			if (cur != null) {
				stack.push(cur);
				System.out.println(cur.e);
				cur = cur.left;
			} else {
				cur = stack.pop();
				cur = cur.right;
			}
		}
	}

	// 二分搜索树的中序遍历
	public void inOrder() {
		inOrder(root);
	}

	// 中序遍历以node为根的二分搜索树, 递归算法
	private void inOrder(Node node) {
		if (node == null)
			return;

		inOrder(node.left);
		System.out.println(node.e);
		inOrder(node.right);
	}

	/* Classic Non-Recursive algorithm for inorder traversal */
	// Time Complexity: O(n), n is the node number in the tree
	// Space Complexity: O(h), h is the height of the tree
	public List<E> inorderTraversal1(Node root) {

		ArrayList<E> res = new ArrayList<E>();
		if (root == null)
			return res;

		Stack<Node> stack = new Stack<>();
		Node cur = root;
		while (cur != null || !stack.empty()) {

			while (cur != null) {
				stack.push(cur);
				cur = cur.left;
			}

			cur = stack.pop();
			res.add(cur.e);
			cur = cur.right;
		}
		return res;
	}

	// NR
	public List<E> inorderTraversal2(Node root) {

		ArrayList<E> res = new ArrayList<E>();
		if (root == null)
			return res;

		Stack<Node> stack = new Stack<>();
		Node cur = root;
		// 这实质上就是模拟了一遍系统栈对 递归实现 的执行过程呀！！
		while (cur != null || !stack.empty()) {// “||”也可以理解为 一个条件成立 执行对立语句之一 直到这个条件不成立时再看另一个条件 执行另一个对立语句 直到另一个条件不成立
												// 对立语句可以用if-else来构造，也可以用while(true){}-false构造（solution1所示）。
			if (cur != null) {
				stack.push(cur);
				cur = cur.left;// 直捣黄龙，找到最最最left的节点，之后就好说了，因为通过节点得到其左右孩子，所以在栈中只要排好left节点顺序就ok了。
			} else {
				cur = stack.pop();//
				res.add(cur.e);
				cur = cur.right;// 每次的出栈都是拿出来一个‘根’节点，只有cur不是叶子节点的时候cur.right才可能不是null，只要不是null就会入栈，接着把该right节点为根的子树重复了一遍之前的过程。
			}
		}
		return res;
	}

	// 二分搜索树的后序遍历
	public void postOrder() {
		postOrder(root);
	}

	// 后序遍历以node为根的二分搜索树, 递归算法
	private void postOrder(Node node) {

		if (node == null)
			return;

		postOrder(node.left);
		postOrder(node.right);
		System.out.println(node.e);
	}

	// postNR
	public List<E> postorderTraversal(Node root) {
		List<E> res = new ArrayList<E>();
		if (root == null)
			return res;
		Stack<Node> stack = new Stack<>();
		Node cur = root;
		Node pre = null;
		while (cur != null || !stack.empty()) {
			// 这是自己改写的代码，对比发现和solution5基本一模一样，但是5里多了一个pre变量。。。难道是哪儿还有问题
			while (cur != null) {
				stack.push(cur);
				cur = cur.left;
			}
			cur = stack.pop();
			if (cur.right != null && pre != cur.right) {
				stack.push(cur);
				pre = cur;
				cur = cur.right;
			} 
			else {
				res.add(cur.e);
				cur = null;// cur被赋予了pop出来的值，要记得重置为null表示树的所有元素已经存完了。前边的两个判断都进不去
			}

		}
		return res;
	}

	// 二分搜索树的层序遍历
	public void levelOrder() {

		Queue<Node> q = new LinkedList<>();
		q.add(root);
		while (!q.isEmpty()) {
			Node cur = q.remove();
			System.out.println(cur.e);

			if (cur.left != null)
				q.add(cur.left);
			if (cur.right != null)
				q.add(cur.right);
		}
	}

	// 寻找二分搜索树的最小元素
	public E minimum() {
		if (size == 0)
			throw new IllegalArgumentException("BST is empty!");

		return minimum(root).e;
	}

	// 返回以node为根的二分搜索树的最小值所在的节点
	private Node minimum(Node node) {
		if (node.left == null)
			return node;
		return minimum(node.left);
	}

	// 寻找二分搜索树的最大元素
	public E maximum() {
		if (size == 0)
			throw new IllegalArgumentException("BST is empty");

		return maximum(root).e;
	}

	// 返回以node为根的二分搜索树的最大值所在的节点
	private Node maximum(Node node) {
		if (node.right == null)
			return node;

		return maximum(node.right);
	}

	// 从二分搜索树中删除最小值所在节点, 返回最小值
	public E removeMin() {
		E ret = minimum();
		root = removeMin(root);
		return ret;
	}

	// 删除掉以node为根的二分搜索树中的最小节点
	// 返回删除节点后新的二分搜索树的根
	private Node removeMin(Node node) {

		if (node.left == null) {
			Node rightNode = node.right;
			node.right = null;
			size--;
			return rightNode;
		}

		node.left = removeMin(node.left);
		return node;
	}

	// 从二分搜索树中删除最大值所在节点
	public E removeMax() {
		E ret = maximum();
		root = removeMax(root);
		return ret;
	}

	// 删除掉以node为根的二分搜索树中的最大节点
	// 返回删除节点后新的二分搜索树的根
	private Node removeMax(Node node) {

		if (node.right == null) {
			Node leftNode = node.left;
			node.left = null;
			size--;
			return leftNode;
		}

		node.right = removeMax(node.right);
		return node;
	}

	// 从二分搜索树中删除元素为e的节点
	public void remove(E e) {
		root = remove(root, e);
	}

	// 删除掉以node为根的二分搜索树中值为e的节点, 递归算法
	// 返回删除节点后新的二分搜索树的根  返回根是因为删除后root可能会改变 即root就是目标
	private Node remove(Node node, E e) {

		if (node == null)
			return null;

		if (e.compareTo(node.e) < 0) {
			node.left = remove(node.left, e);
			return node;
		} else if (e.compareTo(node.e) > 0) {
			node.right = remove(node.right, e);
			return node;
		} else { // e.compareTo(node.e) == 0

			// 待删除节点左子树为空的情况
			if (node.left == null) {
				Node rightNode = node.right;
				node.right = null;
				size--;
				return rightNode;
			}

			// 待删除节点右子树为空的情况
			if (node.right == null) {
				Node leftNode = node.left;
				node.left = null;
				size--;
				return leftNode;
			}

			// 待删除节点左右子树均不为空的情况

			// 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
			// 用这个节点顶替待删除节点的位置
			//successor：后继
			Node successor = minimum(node.right);
			successor.right = removeMin(node.right);
			size++;//此时removeMin(node.right); 这里的语意其实是找到最小值，先不删除
			successor.left = node.left;

			node.left = node.right = null;
			size--;//此时删除了目的节点 size--
			return successor;   

			//最后这段代码是为了练习，实际只需要交换值即可。
		}
	}

	@Override
	public String toString() {
		StringBuilder res = new StringBuilder();
		generateBSTString(root, 0, res);
		return res.toString();
	}

	// 生成以node为根节点，深度为depth的描述二叉树的字符串
	private void generateBSTString(Node node, int depth, StringBuilder res) {

		if (node == null) {
			res.append(generateDepthString(depth) + "null\n");
			return;
		}

		res.append(generateDepthString(depth) + node.e + "\n");
		generateBSTString(node.left, depth + 1, res);
		generateBSTString(node.right, depth + 1, res);
	}

	private String generateDepthString(int depth) {
		StringBuilder res = new StringBuilder();
		for (int i = 0; i < depth; i++)
			res.append("--");
		return res.toString();
	}
}
